# class Solution:
#     def subarraySum(self, nums: List[int], k: int) -> int:
#         n=len(nums)
#         stack=[0]*n
#         ret=0
#         for i in range(n):
#             for j in range(i+1):
#                 stack[j]+=nums[i]
#                 if stack[j]==k:
#                     ret+=1
#         return ret

'''
超时
'''


# class Solution:
#     def subarraySum(self, nums: List[int], k: int) -> int:
#         mapper={}
#         n=len(nums)
#         temp=[0]*n
#         now=0
#         for i in range(n):
#             now+=nums[i]
#             temp[i]=now
#             if now in mapper:
#                 mapper[now].append(i)
#             else:
#                 mapper[now]=[i]
#         ret=0
#         for i in range(n):
#             t=k+temp[i]
#             if t in mapper: 
#                 g=0
#                 s=mapper[t]
#                 while g<len(s) and s[g]<=i:
#                     g+=1
#                 ret+=len(s)-g
#             if k==temp[i]:
#                 ret+=1
#         return ret

'''
超时
'''

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        mapper={}
        n=len(nums)
        now=0
        ret=0
        mapper[0]=1
        for i in range(n):
            now+=nums[i]
            if now-k in mapper:
                ret+=mapper[now-k]
            if now in mapper:
                mapper[now]+=1
            else:
                mapper[now]=1
        return ret

# 执行用时：
# 68 ms
# , 在所有 Python3 提交中击败了
# 99.85%
# 的用户
# 内存消耗：
# 17 MB
# , 在所有 Python3 提交中击败了
# 45.26%
# 的用户